1. Technical Field
The present invention relates generally to wireless communication networks, and more particularly, to controlling call scheduling in satellite and land based wireless communication networks.
2. Related Art
Wireless networks typically comprise a plurality of switching centers, base stations and mobile stations all coupled through wireline and wireless communication links to create communication channels from an originating unit to a terminating unit. Moreover, these cellular networks themselves are coupled to a plurality of wireline networks including the public switched telephone network (PSTN), the Internet, local area networks (LANs) and private branch exchanges (PBXs). The Internet itself is a plurality of data networks coupled together.
An increasing trend includes coupling each of these and other networks through gateway systems, as they are developed to allow any one device to communicate with any other device to exchange communication signals. Accordingly, the various networks are being developed to provide interface ports to create signal paths and communication links from points to other points. Thus, in the context of creating cellular networks, several issues are presented that affect how well a wireless terminal can communicate effectively with these other networks.
One issue is a basic one; namely, there is a need for data streams and, more generally, communication signals to be transported through the cellular network in a reliable manner. In addition to communication signals being transported reliably, there also exists a need to maximize communication network throughput so that a subscriber""s communication signals will have the opportunity to be transported reliably, especially at times of peak usage. There is a continuous need, therefore, to maximize communication network efficiencies.
Whether the wireless communication network is a type of land based (terrestrial) network, for example North American Time Division Multiple Access (TDMA) or Global System for Mobile Communications (GSM), or a satellite based communication network, the need for maximizing the networks"" efficiency and throughput exists. Along these lines, as some of these wireless networks age and become somewhat less capable in relation to newer networks having higher throughput capacity, there will be a need to extend their capacities to extend their useful lives.
The motivation to increase capacity is not limited to older communication networks. There is an ongoing need to maximize return on investment in infrastructure because communication networks are very expensive. Thus, there exists a need to maximize efficiency even in the newer, higher capacity networks. Moreover, the implementation of efficient systems reduces, in some cases, the size or amount of circuitry required to handle the communication throughput requirements.
In the context of maximizing efficiency in a wireless communication network, there exists a need to maximize the number of subscriber requests granted. To meet this need, the subscribers are ranked based on the requested number of time periods, or time slices, at a given frequency (hereinafter, xe2x80x9ccommunication channelsxe2x80x9d). In current systems, resource allocation is relatively simple but inefficient. Simply described, subscribers are assigned resources on a first-come-first-served-basis if the resources are available and easily identified.
Accordingly, two basic types of inefficiencies are introduced with this approach. First, with sessions continually coming into and terminating from the network, the available pool, hereafter called the xe2x80x98Resource Allocation Tablexe2x80x99 (RAT), of communication channels becomes increasingly fragmented. This will be demonstrated later. When this happens, it becomes more difficult to identify available communication channels when subscriber requests are made for multiple communication channels. The problem of how to optimally assign resources for each successive request for service can be solved using an Operations Research technique called xe2x80x9cInteger Programmingxe2x80x9d (IP). However solving IP problems are very time consuming and are generally not solvable in real time (as required in this environment). Consequently, there will be requests that are rejected when resources may be available but not easily identified.
The second type of inefficiency in current systems comes from the fact that resource allocation decisions are being made with incomplete information. In the Operations Research discipline called xe2x80x98Scheduling Theoryxe2x80x99, xe2x80x9conline schedulingxe2x80x9d is characterized by the first-come-first-serve approach described above. Decisions are made whether to accept a request for communication channels, and which specific channels to assign to the request, as soon the request is received without knowledge of requests which will arrive later during the predefined period.
What is needed, therefore, is a system that minimizes the problem of communication channel fragmentation and that improves allocation efficiencies.
To overcome the shortcomings of the prior systems and their operations, the present invention contemplates an apparatus and a method for allocating communication channels in a manner that increases network efficiencies and operator revenue by implementing offline scheduling. Offline scheduling is the task of assigning communication channel resources only after complete knowledge of the requests made during a predefined period of time, tp. Requests for communication channels are formed in a queue for a specified time period (tp). Thereafter, notification of communication channel assignments are returned to the requester. By utilizing a resource manager that waits until all information is available before allocating resources, communication channel allocations may be made more efficiently and, at the same time, may minimize the fragmentation problem described above.
Stated simply, a resource manager accepts and stores (forms a queue) resource requests for a brief period of time and then allocates resources according to specified criteria. The invention herein may be used in any wireless communication network including satellite-based communication networks. Accordingly, the throughput of any network may be increased thereby increasing its useful life and increasing the short and long term revenue for the given network.
After creating a queue of resource requests, the resource manager. (RM) allocates communication channels in a manner that maximizes the number of requests for communication channel resources that are satisfied by giving priority in reverse order of the size of the request. In some embodiments, the RM alternately evaluates the value of connection requests, and allocates communication channels in a manner that increases revenue.
By forming a queue of resource requests before assigning communication channels, the RM is able to select a combination of communication channel assignments that improves efficiency and that increases either the number of requests that are filled or the revenue according to the objective of the network operator.
As will be detailed below, after forming a queue of resource requests for time period tp, the RM allocates communication channels in the following order:
(a) to legacy continuous bit rate (CBR) subscribers;
(b) to ongoing legacy non-CBR; and
(c) to new CBR subscribers.
This will be done in such a way as to leave a single contiguous range in the RAT for the assignment of the new non-CBR subscribers. After complementing the resource allocations as described in (a) through (c) above, the RM will then:
(d) allocate communication channels to the new non-CBR subscribers requesting communication channels in such a way as to either maximize the number of connections, the revenue to be realized from the connection requests granted or the throughput efficiency of the communication channels.
In one embodiment of the invention, communication channel resources are allocated to the new non-CBR requests according to a priority value based upon joint consideration of the revenue to be realized by accepting the connection request and the amount of requested resources. In this embodiment, a revenue ratings is assigned to each request for resources. Additionally, the number of requested communication channels is calculated. Thus, after the CBR requests and legacy non-CBR requests for signal resources are satisfied, requests are ranked by unit revenue value. A quotient of the revenue rating divided by the quantity defines the unit revenue. The unit revenue is used for determining priority.
This problem is recognized in Operations Research as a computationally complex problem called the xe2x80x98Knapsack Problemxe2x80x99 where the task is to select the combination of connections that maximize the sum of the revenues represented by the accepted connections without violating the limit represented by the number of available communication channels in the RAT. A heuristic algorithm is used to determine a near optimal solution to this Knapsack Problem in linear time, thereby making it practical to use in making real time resource allocation decisions.
In another embodiment of the invention, communication channel resources are allocated according to a priority value based only upon the amount of requested resources. In this embodiment, the number of requested communication channels is calculated. Thus, after the CBR requests and legacy non-CBR requests for signal resources are satisfied, new non-CBR requests are assigned based on the signal resources requested.
This problem is recognized in Operations Research literature, as a xe2x80x9cJob-Shop Scheduling Problemxe2x80x9d with the objective of minimizing the number of xe2x80x98tardy jobsxe2x80x99. This involves only the need to rank the requests in increasing order of the quantity of resources that are requested in real time. In yet another embodiment, the requests are ranked in order of decreasing request size in view of remaining resources to maximize throughput efficiency.
Other aspects of the present invention will become apparent with further reference to the drawings and specification that follow.